#include <iostream>
#include <vector>
#include <deque>

using namespace std;
// 239. 滑动窗口最大值
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。

// 使用双端队列。滑动窗口不断向前滑动
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;    // 存放结果
        deque<int> window;  // 存放当前滑动窗口的下标
        if(k == 1) {
            return nums;
        }
        for(int i = 0; i < nums.size(); i++) {
            // 缩小窗口，处理出界
            if(!window.empty() && window.front() <= i-k)
                window.pop_front(); // 窗口往右滑动，最左边的元素出队
            // 扩大窗口
            // 下一个要加入的元素nums[i]大于队列中的元素，则队列的元素要出队
            while(!window.empty() && nums[window.back()] <= nums[i])
                window.pop_back();

            window.push_back(i);    // 下标入队
            // 取队头更新答案
            if(i >= k-1 )
                ans.push_back(nums[window.front()]);

        }
        return ans;
    }

private:
    void printSlidingWindow(deque<int>& window) {
        cout << "window: [ ";
        for(int i = 0; i < window.size(); i++) {
            cout<<window[i];
            if(i != window.size() - 1) {
                cout<<", ";
            }
        }
        cout << " ]" << endl;
    }
};
void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}
int main() {
    vector<int> nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums1, 3)); // 3,3,5,5,6,7

    vector<int> nums2 = {1, -1};
    print_vec(Solution().maxSlidingWindow(nums2,1));  // 1 -1

    vector<int> nums3 = {7,2,4};
    print_vec(Solution().maxSlidingWindow(nums3,2));    // 7 4
    return 0;
}
